/*
 * Graph.h
 *
 *  Created on: Sep 11, 2011
 *      Author: correa
 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <cstdio>
#include "AdjMatrix.h"

#define GSTERR_NEGATIVE_SURPLUS 						1

#define GSHERR_GRAPH_HAS_BEEN_LOADED_ALREADY 				1
#define GSHERR_ANTINEIGHBORHOOD_HAS_BEEN_SET_ALREADY		2
#define GSHERR_ANTINEIGHBORHOOD_SIZE_HAS_BEEN_SET_ALREADY	3
#define GSHERR_NEIGHBORHOOD_HAS_BEEN_SET_ALREADY			4
#define GSHERR_NEIGHBORHOOD_SIZE_HAS_BEEN_SET_ALREADY		5
#define GSHERR_VERTICES_IN_ORDER_ALREADY					6
#define GSHERR_CODE_NOT_VALID								7

typedef enum GT { GT_GRAPH, GT_COMPLEMENT } graphType;

template <class W=int>
class Weight {
public:
	virtual ~Weight() {};

	virtual W	weight(const int i);
	virtual W	weight(const int i, const int j);
	virtual const W *	toarray(int begin, int end);
	virtual const W **toarray(int rbegin, int cbegin, int rend, int cend);
};

template <>
inline int Weight<int>::weight(const int i) {
	return 1;
}

template <>
inline int Weight<int>::weight(const int i, const int j) {
	return 1;
}

template <>
inline double Weight<double>::weight(const int i) {
	return 1.0;
}

template <>
inline double Weight<double>::weight(const int i, const int j) {
	return 1.0;
}

template <class W>
inline const W * Weight<W>::toarray(int begin, int end) {
	return NULL;
}

template <class W>
inline const W ** Weight<W>::toarray(int rbegin, int cbegin, int rend, int cend) {
	return NULL;
}

template <class G>
class GraphFactory {
public:
	GraphFactory() {};
    // Static class to create objects
    // Change is required only in this function to create a new object type
	static G * create(int n) { return new G(n); };
};

class Graph : public AdjMatrix {
	template <class G> friend class GraphFactory;
protected:
	Graph() {};
	Graph(int n);
	Graph(Graph * bg);
public:
	~Graph() {};

	virtual Graph * 	clone();
	virtual Graph * 	homomorphism(const int ar, const int * aR);
	virtual bool		reorder(const int ar, int * const aR);
	virtual Graph * 	complement();
};

inline bool Graph::reorder(const int ar, int * const aR) {
	return false;
}

// methods implemented using a separate Weight interface
template <class W=int>
class WGraphs {
public:
	static int greedySort(Graph * const g, Weight<W> * w, const int * d, int ** ng, const int k, int * rank);
	static int greedyCoverSort(Graph * const g, Weight<W> * w, const int k, int * rank);
	static int dsaturSort(Graph * const g, Weight<W> * w, const int * d, int ** ng, const int k, int * rank);
	static int dsaturCoverSort(Graph * const g, Weight<W> * w, const int k, int * rank);
	static int dsaturFracColoringSort(Graph * const g, Weight<W> * x, int * r, int ** R, const int k, int ** cover);
};

// methods implemented considering unit weights
class Graphs {
public:
	static int greedySort(Graph * const g, const int * d, int ** ng, const int k, int * rank);
	static int greedyCoverSort(Graph * const g, const int k, int * rank);
	static int dsaturSort(Graph * const g, const int * d, int ** ng, const int k, int * rank);
	static int dsaturCoverSort(Graph * const g, const int k, int * rank);
	static int mcrSort(Graph * const g, const int * d, int ** ng, int * rank);
	static int mcrDegreeSort(Graph * const g, int * rank);
	template <class G>
	static G * readDimacsGraph(FILE * graphFile, const graphType t, GraphFactory<G> * fact);
};

#endif /* GRAPH_H_ */
